package jmpo.col;

import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Map - это отдельный интерфейс в JCF, который не иммет общего предка с 
 * Iterable или Collection. Map представляет не набор элементов, а отображение
 * из одного множества элементов (Ключей; Key) в другое множество - значения
 * (Values). Такие структуры принято называть <<ассоциативные массивы>>.
 * 
 * Два основных класса, реализующие возможности интерфейса Map - это 
 *     HashMap - поддержка хеш-таблицы
 *     TreeMap - поддержка сбалансированного бинарного дерева
 * 
 * HashMap - представляет собой неупорядоченный набор ключей
 * TreeMap - может работать только над упорядоченными ключами
 */
/**
 * Рассмотрим простую задачу, которая может потребовать от нас построения Map:
 * В системе построения маршрутов есть специальный класс Leg, который содержит
 * только два элемента: final String to и final String from, куда и откуда 
 * ведёт данная часть маршрута, соответственно. Полный маршрут представляет 
 * собой список List<Leg>. Правильный список устроен таким образом, что 
 * для двух подряд идущих Leg у них совпадают пункты отправления и прибытия:
 * Leg{"Москва", "Казань"} -> Leg{"Казань", "Уфа"}. Требуется написать статический
 * метод, который принимает на вход список Leg и возвращает верный список. 
 * Известно, что входящий список изначально был верный, но в из-за программной 
 * ошибки некоторые участки поменялись местами. Т.е. нам необходимо переставить 
 * элементы так, чтобы порядок был вновь верным.
 * 
 * Простая сортировка ничего нам не даст, так как мы не можем установить свойство
 * транзитивности над двумя произвольными элементами, мы может только прямым сравнением
 * установить являются ли они последовательными. 
 */


final class ProblemA {
    public static final class Leg {
        Leg(String from, String to) { this.from = from; this.to = to; }
        public final String from;
        public final String to;
    
        @Override
        public String toString() {
            return String.format("{ %s -> %s}", from, to);
        }
    }

    public static List<Leg> goodLegList(List<Leg> lst) {
        if (lst.isEmpty()) return lst;
        Map<String, Leg> fromMap = new HashMap<>();
        Map<String, Leg> toMap = new HashMap<>();
        for (var l : lst) {
            fromMap.put(l.from, l); // элементы добавляются вызовом put
            toMap.put(l.to, l);
        }

        LinkedList<Leg> result = new LinkedList<>();
        Deque<Leg> resultingQueue = result;
        var l = lst.getFirst();
        resultingQueue.addFirst(l);
        // проход в конец
        while (fromMap.containsKey(l.to)) { // containsKey проверяет наличие элемента с заданным ключом
            l = fromMap.get(l.to); // get возвращает связанный объект или выбрасывает исключение
            resultingQueue.addLast(l);
        }
        // проход в начало
        l = lst.getFirst();
        while (toMap.containsKey(l.from)) {
            l = toMap.get(l.from);
            resultingQueue.addFirst(l);
        }

        return (List<Leg>)result;        
    }

    public static void test() {
        // A B C D E
        List<Leg> lst = List.of(new Leg("C", "D"), new Leg("E", "F"),  new Leg("B", "C"), new Leg("A", "B"), new Leg("D", "E"));
        var goodLst = goodLegList(lst);
        System.out.println(goodLst);
    }
}

/**
 * Даны две строки. Существует ли отображение символов f: char -> char, которое удовлетворяет двум правилам:
 *     для разных символов отображение задаёт разные разначения,
 *     посимвольное применение отображения к первой строке даёт вторую строку.
 * 
 * В этой задаче достаточно формировать само отображение через Map посимвольно двигаясь в первой строке.
 * В процессе формирования может нарушиться одно из условий:
 *     либо один символ переходит в два разных,
 *     либо для двух разных символов отображение даст одинаковый результат
 */
final class ProblemB {
    public static boolean check(String A, String B) {
        // очевидно, что длина строк должна быть одинаковой
        if (A.length() != B.length()) return false;

        // само отображение
        Map<Character, Character> map = new HashMap<>(); // не забываем, что примитивные типы нужно оборачивать
        // множество букв, для которых уже существует прообраз
        Set<Character> set = new HashSet<>();
        
        for (int idx = 0; idx != A.length(); ++idx) {
            // нарушается первое условие, символ уже получил образ, но он не соответствует ожидаемому строкой B
            if (map.containsKey(A.charAt(idx)) && B.charAt(idx) != map.get(A.charAt(idx))) return false;

            // нарушается второе условие: мы ещё не добавляли этот символ в качестве прообраза, но образ уже добавлен
            if (!map.containsKey(A.charAt(idx)) && set.contains(B.charAt(idx))) return false;

            map.put(A.charAt(idx), B.charAt(idx)); // возможно, что точно такая пара уже была добавлена, но это не влияет на время работы, так как будет переписана ссылка на содежимое пары
            set.add(B.charAt(idx)); // возможно мы уже добавляли этот элемента для такой же пары, но это не повлияет на время работы
        }

        return true;
    }

    public static void test() {
        System.out.println(check("egg", "add")); // expected true
        System.out.println(check("abc", "xyz")); // expected true
        System.out.println(check("egd", "add")); // expected false
        System.out.println(check("egg", "adc")); // expected false
    }
}

record Event(java.time.LocalDate date, String title, String description) { }

public class MapCollection {
    public static void main(String[] args) {
        if (false) ProblemA.test();
        if (false) ProblemB.test();
    }
}
